#include <iostream>
#include "heap.h"

namespace my_heap {

#define MinData (-32767)
#define MinPQSize (10)
 
PriorityQueue Initialize(int MaxElements){
    PriorityQueue H;
 
    if(MaxElements < MinPQSize){
        printf("Priority queue size is too small");
        exit(-1);
    }
 
    H = new HeapStruct;
    if(H == NULL){
        printf("failed to alloc memory space for HeapStruct");
        exit(-1);
    }
 
    /* allocate the array plus one extra for sentinel  */
    H->Elements = new ElementType[MaxElements + 1];
    if(H->Elements == NULL){
        printf("failed to allocate memory for Elements array");
        exit(-1);
    }
 
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData; //此处设置哨兵
 
    return H;
}
 
void Destroy(PriorityQueue H){
    free(H->Elements);
    free(H);
}
 
void MakeEmpty(PriorityQueue H){
    H->Size = 0;
}
 
void Insert(ElementType X, PriorityQueue H){
    int i;
 
    if(IsFull(H)){
        printf("Priority queue is full");
        return;
    }
 
    //从尾部向头部检查
    for(i=++H->Size; H->Elements[i/2]>X; i/=2){
        H->Elements[i] = H->Elements[i/2];
    }
    H->Elements[i] = X;
}
 
ElementType DeleteMin(PriorityQueue H){
    int i,Child;
    ElementType MinElement, LastElement;
 
    if(IsEmpty(H)){
        printf("FATAL: Priority queue is empty");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];
 
    for(i=1; i * 2 <= H->Size; i=Child){
        /*Find smaller child*/
        Child = i * 2;
        if(Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
            Child++;
 
        /*Percolate one level */
        //此时最后一个元素已经在堆顶部了，头部与最后一个元素交换过了
        if(LastElement > H->Elements[Child])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
 
    return MinElement;
}
 
ElementType FindMin(PriorityQueue H){
    if(!IsEmpty(H))
        return H->Elements[1];
    printf("FATAL: Priority queue is Empty");
    return H->Elements[0];
}
 
int IsEmpty(PriorityQueue H){
    return H->Size == 0;
}
 
int IsFull(PriorityQueue H){
    return H->Size == H->Capacity;
}

void PrintTree(const std::string& prefix, const PriorityQueue root, int i = 1, int dir = 0) {
    if (root && i <= root->Size) {
        std::cout << prefix;
        std::string newPrefix = prefix;
        if (dir == 1) {
            std::cout << "├──";
            newPrefix += "│  ";
        }
        else if (dir == 2) {
            std::cout << "└──";
            newPrefix += "   ";
        }
        std::cout << root->Elements[i] << std::endl;

        PrintTree(newPrefix, root, i*2, 1);
        PrintTree(newPrefix, root, i*2+1, 2);
    }
}

typedef Heap<int> HeapInt;
void Handle(){
    int i, NUM=30;
    PriorityQueue pq = Initialize(NUM);
    for(i=0; i<NUM; i++)
        Insert(i, pq);

    PrintTree("", pq);
 
    std::cout << "delete element: ";
    for(i=0; i<10; i++){
        ElementType t = DeleteMin(pq);
        std::cout << t << ",";
    }
    std::cout << std::endl;

    PrintTree("", pq);

    HeapInt *hp = new HeapInt(2);
    hp->push(1, 2);
    hp->push(2, 3);
    hp->push(4, 5);
    std::cout << "heap top " << hp->top() << std::endl;
}

}

void HandleHeap() {
    my_heap::Handle();
}

